package com.zyk.grate_offer.class10;

/**
 * 二叉搜索树, 转双向链表
 * left = last
 * right = next
 *
 * 普遍位置按搜索二叉树中序顺序连
 * start.last = end
 * end.next = start
 *
 * @author zhangsan
 * @date 2021/5/30 12:01
 */
public class Code03_BSTtoDoubleLinkedList {

    static class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val,Node _left,Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    }


    static Node pre, head;

    // dfs 搞
    public static Node treeToDoublyList(Node root) {
        if (root == null) {
            return null;
        }
        dfs(root);
        head.left = pre;
        pre.right = head;
        return head;
    }

    public static void dfs(Node cur) {
        if (cur == null) {
            return;
        }
        dfs(cur.left);
        if (pre != null) {
            pre.right = cur;
        } else {
            head = cur;
        }
        cur.left = pre;
        pre = cur;
        dfs(cur.right);
    }

    // 二叉树递归套路解
    public static Node treeToDoublyList2(Node root) {
        Info info = process(root);
        info.start.left = info.end;
        info.end.right = info.start;
        return info.start;
    }

    public static Info process(Node cur) {
        if(cur == null) return new Info(null, null);

        Info lInfo = process(cur.left);
        Info rInfo = process(cur.right);
        Node start = cur, end = cur;
        // 把当前节点串好
        if(lInfo.start != null) {
            start = lInfo.start;
            lInfo.end.right = cur;
            cur.left = lInfo.end;
        }
        if(rInfo.end != null) {
            end = rInfo.end;
            cur.right = rInfo.start;
            rInfo.start.left = cur;
        }

        return new Info(start, end);
    }

    public static class Info {
        Node start;
        Node end;

        public Info(Node start, Node end) {
            this.start = start;
            this.end = end;
        }
    }

}
